home *** CD-ROM | disk | FTP | other *** search
/ Windows Expert / Windows Expert.iso / program / segheap.zip / SEGHEAP.C next >
C/C++ Source or Header  |  1992-02-16  |  8KB  |  347 lines
  1. /* Routines for the SEGHEAP library     */
  2. /* Copyright (C) Stephen Chung, 1992.   */
  3. /* All rights reserved.                 */
  4.  
  5. #include <windows.h>
  6. #include <stdarg.h>
  7.  
  8. #define MAGIC           0x42022667
  9.  
  10. typedef struct MemoryStruct {
  11.     long int magic;
  12.     void far *page;
  13.     unsigned int size;
  14.     BOOL allocated;
  15.     struct MemoryStruct far *next, far *prev;
  16. } MEMHEADER;
  17.  
  18. typedef struct PageHeaderStruct {
  19.     long int magic;
  20.     HANDLE handle;
  21.     unsigned int size;
  22.     unsigned int used;
  23.     unsigned int overhead;
  24.     MEMHEADER far *data, far *empty;
  25.     struct PageHeaderStruct far *next, far *prev;
  26. } MEMPAGEHEADER;
  27.  
  28. typedef struct {
  29.     MEMPAGEHEADER far *pages;
  30.     int nr_pages;
  31. } MAINMEMHEADER;
  32.  
  33. #define PAGESIZE        (4 * 1024)
  34. #define USEABLESIZE     (PAGESIZE - sizeof(MEMPAGEHEADER) - sizeof(MEMHEADER))
  35.  
  36.  
  37. static MAINMEMHEADER header = { NULL, 0 };
  38.  
  39.  
  40.  
  41. static void Error(char *fmt, ...)
  42. {
  43.     va_list argptr;
  44.     char buffer[1024];
  45.  
  46.     va_start(argptr, fmt);
  47.     vsprintf(buffer, fmt, argptr);
  48.     va_end(argptr);
  49.  
  50.     MessageBeep(0);
  51.     MessageBox (NULL, buffer, "Error Message", MB_ICONEXCLAMATION | MB_OK);
  52. }
  53.  
  54.  
  55.  
  56. static MEMPAGEHEADER far *AddPage(unsigned int n)
  57. {
  58.     void far *cp;
  59.     MEMHEADER far *mp;
  60.     MEMPAGEHEADER far *p;
  61.     HANDLE handle = NULL;
  62.  
  63.     handle = GlobalAlloc(GMEM_MOVEABLE, n);
  64.     if (handle == NULL) {
  65.         Error("Out of memory: allocating %d bytes", n);
  66.         return (NULL);
  67.     }
  68.  
  69.     if (header.pages == NULL || header.nr_pages <= 0) {
  70.         p = header.pages = (MEMPAGEHEADER far *) GlobalLock(handle);
  71.         p->prev = NULL;
  72.     } else {
  73.         for (p = header.pages; p->next != NULL; p = p->next);
  74.         p->next = (MEMPAGEHEADER far *) GlobalLock(handle);
  75.         p->next->prev = p;
  76.         p = p->next;
  77.     }
  78.  
  79.     p->magic = MAGIC;
  80.     p->handle = handle;
  81.     p->next = NULL;
  82.     p->size = n;
  83.     p->used = 0;
  84.     p->overhead = sizeof(MEMPAGEHEADER) + sizeof(MEMHEADER);
  85.  
  86.     cp = ((char far *) p) + sizeof(MEMPAGEHEADER);
  87.     mp = (MEMHEADER far *) cp;
  88.  
  89.     p->data = p->empty = mp;
  90.  
  91.     mp->magic = 0L;
  92.     mp->allocated = FALSE;
  93.     mp->page = p;
  94.     mp->size = p->size - p->overhead;
  95.     mp->next = mp->prev = NULL;
  96.  
  97.     header.nr_pages++;
  98.  
  99.     return (p);
  100. }
  101.  
  102.  
  103.  
  104. static void DeletePage (MEMPAGEHEADER far *p)
  105. {
  106.     if (p->next == NULL && p->prev == NULL) {
  107.         header.pages = NULL;
  108.         header.nr_pages = 0;
  109.         GlobalFree(GlobalUnlock(p->handle));
  110.     } else {
  111.         if (p == header.pages) header.pages = p->next;
  112.         header.nr_pages--;
  113.  
  114.         if (p->prev != NULL) p->prev->next = p->next;
  115.         if (p->next != NULL) p->next->prev = p->prev;
  116.  
  117.         GlobalFree(GlobalUnlock(p->handle));
  118.     }
  119. }
  120.  
  121.  
  122.  
  123. void far *SegHeapAlloc (unsigned int n)
  124. {
  125.     MEMPAGEHEADER far *p;
  126.     MEMHEADER far *mp;
  127.     char far *cp;
  128.  
  129.     if (n >= 65535) {
  130.         Error("MyGlobalAlloc: size (%ud) > 64K!", n);
  131.         return (NULL);
  132.     }
  133.  
  134.     /* Larger than page size? */
  135.  
  136.     if (n > USEABLESIZE) {
  137.         p = AddPage(n + sizeof(MEMPAGEHEADER) + sizeof(MEMHEADER));
  138.  
  139.         mp = p->data;
  140.         mp->magic = MAGIC;
  141.         mp->allocated = TRUE;
  142.  
  143.         p->used = n;
  144.         p->empty = NULL;
  145.  
  146.         cp = ((char far *) mp) + sizeof(MEMHEADER);
  147.         return ((void far *) cp);
  148.     }
  149.  
  150.  
  151.     /* Search for the hole */
  152.  
  153.     for (p = header.pages; p != NULL; p = p->next) {
  154.         /* Scan the chains */
  155.         if (p->size - p->used - p->overhead <= 0) continue;
  156.         if (p->empty == NULL) continue;
  157.  
  158.         for (mp = p->empty; mp != NULL; mp = mp->next) {
  159.             if (!mp->allocated && mp->size >= n) break;
  160.         }
  161.  
  162.         if (mp != NULL) break;
  163.     }
  164.  
  165.     /* New page needed? */
  166.  
  167.     if (p == NULL) {
  168.         p = AddPage(PAGESIZE);
  169.         mp = p->data;
  170.     }
  171.  
  172.     /* Do we need to break it up? */
  173.  
  174.     if (mp->size - n > sizeof(MEMHEADER)) {
  175.         MEMHEADER far *mp2;
  176.  
  177.         cp = ((char far *) mp) + n + sizeof(MEMHEADER);
  178.         mp2 = (MEMHEADER far *) cp;
  179.  
  180.         mp2->magic = 0L;
  181.         mp2->allocated = FALSE;
  182.         mp2->page = p;
  183.         mp2->size = mp->size - n - sizeof(MEMHEADER);
  184.  
  185.         mp2->next = mp->next;
  186.         mp2->prev = mp;
  187.         if (mp->next != NULL) mp->next->prev = mp2;
  188.         mp->next = mp2;
  189.  
  190.  
  191.         p->overhead += sizeof(MEMHEADER);
  192.  
  193.         mp->size = n;
  194.     }
  195.  
  196.     mp->magic = MAGIC;
  197.     mp->allocated = TRUE;
  198.  
  199.     p->used += n;
  200.     cp = ((char far *) mp) + sizeof(MEMHEADER);
  201.  
  202.     /* Search for the next empty hole */
  203.  
  204.     for (; mp != NULL; mp = mp->next) {
  205.         if (!mp->allocated && mp->size > 0) break;
  206.     }
  207.  
  208.     p->empty = mp;
  209.  
  210.     return ((void far *) cp);
  211. }
  212.  
  213.  
  214. void SegHeapFree (void far *vp)
  215. {
  216.     MEMPAGEHEADER far *p;
  217.     MEMHEADER far *mp, far *mp2;
  218.     char far *cp;
  219.  
  220.     cp = ((char far *) vp) - sizeof(MEMHEADER);
  221.     mp = (MEMHEADER far *) cp;
  222.  
  223.     if (mp->magic != MAGIC || !mp->allocated) {
  224.         Error("Trying to deallocate invalid memory block (%Fp)!\n", cp);
  225.         return;
  226.     }
  227.  
  228.     p = (MEMPAGEHEADER far *) mp->page;
  229.     p->used -= mp->size;
  230.  
  231.     mp->magic = 0L;
  232.     mp->allocated = FALSE;
  233.  
  234.     /* Merge? */
  235.  
  236.     mp2 = mp->prev;
  237.  
  238.     if (mp2 != NULL && !mp2->allocated) {
  239.         mp2->next = mp->next;
  240.         if (mp->next != NULL) mp->next->prev = mp2;
  241.         mp2->size += mp->size + sizeof(MEMHEADER);
  242.  
  243.         p->overhead -= sizeof(MEMHEADER);
  244.  
  245.         mp = mp2;
  246.     }
  247.  
  248.     mp2 = mp->next;
  249.  
  250.     if (mp2 != NULL && !mp2->allocated) {
  251.         mp->next = mp2->next;
  252.         if (mp2->next != NULL) mp2->next->prev = mp;
  253.  
  254.         mp->size += mp2->size + sizeof(MEMHEADER);
  255.  
  256.         p->overhead -= sizeof(MEMHEADER);
  257.     }
  258.  
  259.     if (mp->prev == NULL && mp->next == NULL) {
  260.         DeletePage(p);
  261.     } else {
  262.         if (p->empty == NULL || p->empty < mp) p->empty = mp;
  263.     }
  264. }
  265.  
  266.  
  267.  
  268. void far *SegHeapRealloc (void far *p, unsigned int n)
  269. {
  270.     MEMHEADER far *mp;
  271.     char far *cp;
  272.  
  273.     /* Block already large enough? */
  274.  
  275.     cp = ((char far *) p) - sizeof(MEMHEADER);
  276.     mp = (MEMHEADER far *) cp;
  277.  
  278.     if (mp->magic != MAGIC) {
  279.         Error("Error: Trying to reallocate invalid memory block!");
  280.         return (p);
  281.     }
  282.  
  283.     if (mp->size >= n) return (p);      /* No need to do anything */
  284.  
  285.     /* Else swap to another block */
  286.  
  287.     cp = SegHeapAlloc(n);
  288.     memcpy(cp, p, (mp->size >= n) ? n : mp->size);
  289.     SegHeapFree(p);
  290.  
  291.     return ((void far *) cp);
  292. }
  293.  
  294.  
  295.  
  296. void MemoryStatistics (long int *allocated, long int *used)
  297. {
  298.     MEMPAGEHEADER far *p;
  299.  
  300.     *allocated = *used = 0L;
  301.  
  302.     for (p = header.pages; p != NULL; p = p->next) {
  303.         *allocated += p->size;
  304.         *used += p->used + p->overhead;
  305.     }
  306. }
  307.  
  308.  
  309. void FreeAllMemory (void)
  310. {
  311.     MEMPAGEHEADER far *p, far *p1;
  312.  
  313.     for (p = header.pages; p != NULL; ) {
  314.         p1 = p->next;
  315.         GlobalFree(GlobalUnlock(p->handle));
  316.         p = p1;
  317.     }
  318.  
  319.     header.pages = NULL;
  320.     header.nr_pages = 0;
  321. }
  322.  
  323.  
  324. #ifdef DEBUG
  325.  
  326. /* For debugging purposes...  not very pretty */
  327.  
  328. void PrintMemoryChains(void)
  329. {
  330.     MEMPAGEHEADER far *p;
  331.     MEMHEADER far *mp;
  332.     char far *cp;
  333.     char buffer[100];
  334.  
  335.     /* Block already large enough? */
  336.  
  337.  
  338.     for (p = header.pages; p != NULL; p = p->next) {
  339.         for (mp = p->data; mp != NULL; mp = mp->next) {
  340.             sprintf(buffer, "%Fp | %ud | %s", mp, mp->size, mp->allocated ? "Alloc" : "Free");
  341.             MessageBox (NULL, buffer, "Memory Chain", MB_ICONEXCLAMATION | MB_OK);
  342.         }
  343.     }
  344. }
  345.  
  346. #endif DEBUG
  347.